import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-08-20
 * Time: 15:28
 */
public class Test {
    public int minOperations(int[] nums, int x) {
        int sum = 0;
        for(int n : nums) sum += n;  //求数组所有元素的总和
        int target = sum - x;
        if(target < 0) return -1;
        int ret = -1;
        for(int left = 0, right = 0,sum1 = 0; right < nums.length; right++) {
            sum1 += nums[right];
            while(sum1 >= target) {
                if(sum1 == target) {
                    ret = Math.max(ret,right - left + 1);
                }
                sum1 -= nums[left++];
            }
        }

        return ret == -1 ? -1 : nums.length - ret;
    }

    public int totalFruit(int[] fruits) {
        int ret = 1;
        int[] hash = new int[fruits.length];
        for(int left = 0, right = 0,kinds = 0; right < fruits.length; right++) {
            int in = fruits[right];
            if(hash[in]++ == 0) kinds++;
            if(kinds <= 2) {
                ret = Math.max(ret,right - left + 1);
            }
            while(kinds > 2) {
                int out = fruits[left++];
                if(--hash[out] == 0) kinds--;
            }
        }

        return ret;
    }

    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> list = new ArrayList<>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for(char ch : p) hash1[ch - 'a']++;
        int len = p.length;
        for(int left = 0, right = 0,count = 0; right < s.length; right++) {
            char in = s[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            if(right - left + 1 > len) {
                char out = s[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            if(count == len) {
                list.add(left);
            }
        }

        return list;
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        Map<String,Integer> map1 = new HashMap<>();
        for(String tmp : words) {
            map1.put(tmp,map1.getOrDefault(tmp,0) + 1);
        }
        int len = words.length;  //求words数组的大小
        int m = words[0].length();  //求words数组中每个单词的长度
        for(int i = 0; i < m; i++) {
            Map<String,Integer> map2 = new HashMap<>();
            for(int left = i, right = i, count = 0; right <= s.length()-m; right += m) {
                String in = s.substring(right,right + m);
                map2.put(in,map2.getOrDefault(in,0) + 1);
                if(map2.get(in) <= map1.getOrDefault(in,0)) count++;
                if(right - left + 1 > len * m) {
                    String out = s.substring(left,left + m);
                    if(map2.get(out) <= map1.getOrDefault(out,0)) count--;
                    map2.put(out,map2.get(out) - 1);
                    left += m;
                }
                if(count == len) list.add(left);
            }
        }

        return list;
    }
}
